class Solution {
public:
    int dp(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return dp(n-1) + dp(n-2);
    }
    int climbStairs(int n) {
        int p=0, q=0, r=1;
        for (int i = 1; i<=n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
};